import java.util.*;

public class tanxing {

    //10元的要找5原 20的要优先给10原
    //再找20元时就体现了贪心的性质，是要找10原和5原还是直接给3张5原
    //这里可以直到5原可以找出20和10，使用频率会更多，可优先吧频率第的10原给出
    //交换论证法
    //对于贪心解时10 5
    //若最优解时5 5 5 那么也可以将最优解转换为我们的贪心解10，5
    //所以这个算法时正确的
    public boolean lemonadeChange(int[] bills) {
        int count5 = 0;
        int count10 = 0;
        for (int x : bills) {
            if (x == 5) {
                count5++;
            } else if (x == 10) {
                if (count5 == 0) {
                    return false;
                }
                count5--;
                count10++;
            } else if (x == 20) {
                if (count5 != 0 && count10 != 0) {
                    count10--;
                    count5--;
                } else if (count5 >= 3) {
                    count5 -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }

    //每次都减的是最大的数这样就可以以最小次数减少到一半
    //交换论证法
    //若贪心算法是要5次，而最优解是4步
    //那么着重看不相同的那几步，若不相同的是第3步，贪心每次都是除的是最大的数
    //而最优解和他不相同也就是没有用到最大的数，那么可以吧没有用到的最大的数，这样
    //就可以最优解转换为贪心解，而如果没有对调，而最优解只用了4步且不是
    //使用的是每次减少最快的方法就吧总和减少了一半这显然是错误的
    public int halveArray(int[] nums) {
        PriorityQueue<Double> heap = new PriorityQueue<>((a, b) -> b.compareTo(a));//建立大根堆
        double sum = 0;
        for (int a: nums) {
            heap.add((double) a);
            sum += a;
        }
        sum /= 2.0;
        int count = 0;
        while (sum > 0) {
            double val = heap.poll() / 2.0;
            sum -= val;
            heap.offer(val);
            count++;
        }
        return count;
    }

    //排序 贪心体现的点是每次都将i 和 i+1 正反拼接起来，然后比较大小，更大就交换，更小就不管
    //这样每次拼接的都是俩个数之间拼接的最大值，那么最后得到的就是最大的数
    //运行时间比较慢，那么就可换种排序
    public String largestNumber(int[] nums) {
        String[] arr = new String[nums.length];
        int i = 0;
        for (int s : nums) {
            arr[i++] = s + "";
        }

        //对他进行排序
        Arrays.sort(arr,(a,b)->{
            return (b + a).compareTo(a + b);
        });

        StringBuffer ret = new StringBuffer();
        for (String s : arr) {
            ret.append(s);
        }
        if (ret.charAt(0) == '0') {
            return "0";
        }
        return ret.toString();
    }

    /**
     * 摆动序列
     * @param nums
     * @return
     */
    public int wiggleMaxLength(int[] nums) {
        int left =0;
        int ret = 1;
        for (int i = 0; i < nums.length-1; i++) {
            int right = nums[i + 1] - nums[i];//i这位的后一个
            if (right == 0) {
                continue;//这时为平峰 忽略中间的点
            }
            if (right * left <= 0) {//说明左右是不同的峰值 正为升 负为降
                ret++;
                left = right;//将left等于right换到下一种状态
            }
        }
        return ret;
    }

    /**
     * 最长递增子序列
     * 10,9,2,5,3,7,101,18
     * 定义一个dp数组，第一个储存10，9小于10，那么就10更新为9，因为如果后面的数能连接到10的话也一定能
     * 连接到9，且9比10小，能连接的范围更大，在遍历2，发现2又小于9，那么同理又更新为2，接着
     * 5比2大，那么就吧5放到2后面，依此方式向后遍历数组，最终的到的有效数据大小就是最终的最长子序列
     * 在每次遍历dp找到合适的更新位置时，可以使用二分查找来查找dp数组，因为该算法能将dp数组变成一个升序的数组，那么
     * 最终就可以吧这个数组分成俩半
     * @param nums
     * @return
     */

    public int lengthOfLIS(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            if (nums[i] > list.get(list.size() - 1)) {//比所有的都大
                list.add(nums[i]);
            } else {//二分找到插入位置 找到j nums[i]>nums[j-1] nums[i]<=nums[j] 然后将j值 变为i值
                int left = 0;
                int right = list.size() - 1;
                while (right > left) {
                    int mid = (right + left) / 2;
                    if (list.get(mid) < nums[i]) {//mid往右走
                        left = mid + 1;
                    } else {//往左走 没有减一直接是等于最终就会走到最后一个比target小的位置
                        right = mid;
                    }
                }
                list.set(left, nums[i]);
            }
        }
        return list.size();
    }

    /**
     * 递增的三元子序列
     * @param nums
     * @return
     */
    public boolean increasingTriplet(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        int n = nums.length;
        list.add(nums[0]);
        for (int i = 0; i < n; i++) {
            if (nums[i] > list.get(list.size() - 1)) {
                list.add(nums[i]);
            } else {
                int left = 0, right = list.size() - 1;
                while (right > left) {
                    int mid = (right + left) / 2;
                    if (list.get(mid) < nums[i]) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                list.set(left,nums[i]);
            }
            if (list.size() == 3) {
                return true;
            }
        }
        return false;
    }

    public boolean increasingTripletLo(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        for (int x : nums) {
            int i = list.size();
            if (x > list.get(i)) {
                list.add(x);
                if (list.size() == 3) {
                    return true;
                }
            } else if (list.size() == 2 && list.get(i) > x
                    && x > list.get(i - 1)) {
                list.set(i, x);
            } else if (list.get(0) > x) {
                list.set(0, x);
            }
        }
        return false;
    }

    public boolean increasingTripletBe(int[] nums) {
        int a = nums[0], b = Integer.MAX_VALUE;
        for (int x : nums) {
            if(x > b) return true;//比b大了那么就有了第三个
            else if(x > a) b = x;//x比a大更新b这时就有俩个数了
            else a = x;//x比a小，那么就跟新a变为更小的a
        }
        return false;
    }

    /**
     * 最长连续递增序列
     * @param nums
     * @return
     */
    public int findLengthOfLCIS(int[] nums) {
        int ret = 1, tmpL = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                tmpL += 1;
            } else {//不大于就重置
                ret = Math.max(ret, tmpL);//贪心，没有必要一次一次的加ret，在重置tmpL时跟新才是最佳的
                tmpL = 1;
            }
        }
        ret = Math.max(ret, tmpL);
        return ret;
    }
    public int findLengthOfLCISBe(int[] nums) {
        int ret = 1, j = 0;
        for (int i = 0;  i < nums.length;) {
            j = i + 1;
            while (j < nums.length && nums[j] > nums[j - 1]) j++;
            ret = Math.max(ret, j-i);
            i = j;
        }
        return ret;
    }

    /**
     * 买卖股票的最佳时机
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int prevMin = Integer.MAX_VALUE, ret = -1;
        for (int i : prices) {
            prevMin = Math.min(i, prevMin);
            ret = Math.max(i - prevMin, ret);
        }
        return ret;
    }

    //拆分 将每次交易拆分成每天每天的

    /**
     * 买卖股票的最佳实际2
     * @param prices
     * @return
     */
    // 双指针
    public int maxProfit_I(int[] prices) {
        int ret = 0, i = 0, j = 1, n = prices.length;
        for (; j < n; ) {
            if (prices[j] <= prices[j - 1]) {//当天价格比第二天的低
                j++;
                i++;
            }else {
                while (j < n && prices[j - 1] < prices[j]) j++;
                ret += prices[j - 1] - prices[i];
                i = j-1;
            }
        }
        return ret;
    }
    public int maxProfit_II(int[] prices) {
        int ret = 0, i = 0, j = 1, n = prices.length;
        for (; j < n; ) {
            if (prices[j] <= prices[j - 1]) {//当天价格比第二天的低
                j++;
                i++;
            }else {//比他大的情况 
                ret += prices[j] - prices[i];
                j++;
                i++;
            }
        }
        return ret;
    }
}
class tangxing_Text{
    public static void main(String[] args) {
        tanxing t = new tanxing();
        int[] arr = {7,1,5,3,6,4};
        System.out.println(t.maxProfit_II(arr));

    }
}